package main

import (
	"fmt"
	"math"
)

/**
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

利用输入的空间
两个循环
第一个循环将对应位置上的值置为负数
第二个循环检测值为整数的位置，这个位置号+1就是不包含的值
*/
func findDisappearedNumbers(nums []int) []int {

	for _, v := range nums {
		index := int(math.Abs(float64(v))) - 1                   // 这两句容易出错，注意v和nums[index]可能是负值，要去绝对值再操作
		nums[index] = int(math.Abs(float64(nums[index]))) * (-1) //
	}

	var output []int

	for i, v := range nums {
		if v > 0 {
			output = append(output, i+1)
		}
	}

	return output
}

func main() {
	fmt.Println(findDisappearedNumbers([]int{4, 3, 2, 7, 8, 2, 3, 1}))
}
